<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-0 vector-toc-not-available vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-0 skin-theme-clientpref-day vector-sticky-header-enabled" lang="de" dir="ltr"><head>
<meta charset="UTF-8">
<title>Toniann Pitassi</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="icon" type="image/png" href="./_res_/favicon.png">
<link rel="canonical" href="https://de.wikipedia.org/wiki/Toniann_Pitassi"> <link href="./_mw_/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.wikimediamessages.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link href="./_mw_/ext.gadget.citeRef.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.defaultPlainlinks.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonHide.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonLayout.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonStyle.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiDarkmode.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiResponsive.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.specialSearch.css" rel="stylesheet" type="text/css">
<link rel="stylesheet" type="text/css" href="./_mw_/site.styles.css">
<link rel="stylesheet" type="text/css" href="./_mw_/noscript.css">
<link rel="stylesheet" type="text/css" href="./_res_/footer.css">
<link rel="stylesheet" type="text/css" href="./_res_/vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Toniann_Pitassi rootpage-Toniann_Pitassi skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Toniann Pitassi</span></h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="contentSub">
<div id="mw-content-subtitle"></div>
</div>
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">
<p><b>Toniann Pitassi</b> (* in <a href="Pittsburgh" title="Pittsburgh">Pittsburgh</a>) ist eine kanadisch-US-amerikanische Informatikerin.
</p><p>Pitassi studierte an der <a href="Pennsylvania_State_University" title="Pennsylvania State University">Pennsylvania State University</a> mit dem Bachelor- und Master-Abschluss und wurde 1992 an der <a href="University_of_Toronto" title="University of Toronto">University of Toronto</a> bei <a href="Stephen_Cook" class="mw-redirect" title="Stephen Cook">Stephen Cook</a> promoviert (<i>The Complexity of Weak Formal Systems</i>).<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Als <a href="Post-Doktorand" class="mw-redirect" title="Post-Doktorand">Post-Doktorandin</a> war sie zwei Jahre an der <a href="University_of_California%2C_San_Diego" title="University of California, San Diego">University of California, San Diego</a>. Danach war sie zwei Jahre Assistant Professor an der <a href="University_of_Pittsburgh" title="University of Pittsburgh">University of Pittsburgh</a> und anschließend vier Jahre an der <a href="University_of_Arizona" title="University of Arizona">University of Arizona</a>. Ab 2001 war sie Professorin an der University of Toronto (<i>Bell Research Chair</i>) und ab 2021 an der <a href="Columbia_University" title="Columbia University">Columbia University</a> (<i>Jeffrey L. and Brenda Bleustein Professor of Engineering</i>).
</p><p>2017, 2019, 2020 und 2021 war sie als Gastprofessorin am <a href="Institute_for_Advanced_Study" title="Institute for Advanced Study">Institute for Advanced Study</a> (und 2004 Mitglied des IAS).<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>
</p><p>Pitassi befasst sich mit <a href="Komplexit%C3%A4tstheorie" title="Komplexitätstheorie">Komplexitätstheorie</a> und insbesondere Beweis-Komplexität in verschiedenen formalen Systemen der Mathematik (Logik) und Informatik, aber auch zum Beispiel Kommunikationskomplexität und Schaltkreiskomplexität. Eine Motivation für ihre Forschung ist das <a href="P-NP-Problem" title="P-NP-Problem">P-NP-Problem</a>, wozu sie als Vorstufe Beweiskomplexität in Logik-Systemen (und <a href="Erf%C3%BCllbarkeitsproblem_der_Aussagenlogik" title="Erfüllbarkeitsproblem der Aussagenlogik">Erfüllbarkeitsproblemen</a>) untersucht, mit dem zentralen Problem zu untersuchen, welche Tautologien effiziente Beweise in Standard-Beweissystemen besitzen. Dabei wird Effizienz in Zeit, Raum und Zufälligkeit gemessen.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Unter anderem gab sie 1993 mit Paul Beame und <a href="Russell_Impagliazzo" title="Russell Impagliazzo">Russell Impagliazzo</a> exponentieller untere Grenzen für das <a href="Schubfachprinzip" title="Schubfachprinzip">Schubfachprinzip</a> in Frege- bzw. Hilbert-Systemen (Standardsystemen der Beweistheorie). Mit Beame, <a href="Richard_M._Karp" title="Richard M. Karp">Richard M. Karp</a> und <a href="Michael_Saks" title="Michael Saks">Michael Saks</a> bewies sie exponentielle untere Schranken für die Komplexität von Resolutionsbeweisen für dicht verteilte zufällige 3-<a href="Konjunktive_Normalform" title="Konjunktive Normalform">CNF</a> und subexponentielle obere Schranken mit Hilfe des <a href="Davis-Putnam-Verfahren" title="Davis-Putnam-Verfahren">Davis-Putnam-Verfahrens</a>.
</p><p>Sie befasst sich auch mit <a href="Differential_Privacy" title="Differential Privacy">Differential Privacy</a> (die Privatsphäre erhaltene Datenverarbeitungsverfahren), nicht-diskriminierendes <a href="Maschinenlernen" class="mw-redirect" title="Maschinenlernen">Maschinenlernen</a>.
</p><p>2012 erhielt sie den <a href="EATCS-Award" title="EATCS-Award">EATCS-Award</a>. 2018 wurde sie Fellow der <a href="Association_for_Computing_Machinery" title="Association for Computing Machinery">Association for Computing Machinery</a>. 1998 war sie eingeladene Sprecherin auf dem <a href="Internationaler_Mathematikerkongress" title="Internationaler Mathematikerkongress">Internationalen Mathematikerkongress</a> in Berlin (<i>Unsolvable systems of equations and proof theory</i>). 2012 leitete sie das Programmkomitee für das ACM <i>Symposium on Theory of Computing</i> (STOC). 2022 wurde sie Mitglied der <a href="National_Academy_of_Sciences" title="National Academy of Sciences">National Academy of Sciences</a>.
</p><p>Sie ist mit dem Informatikprofessor an der Columbia-University Richard Zemel verheiratet.
</p>
<div class="mw-heading mw-heading2"><h2 id="Schriften_(Auswahl)"><span id="Schriften_.28Auswahl.29"></span>Schriften (Auswahl)</h2></div>
<ul><li>mit Paul Beame, Russell Impagliazzo: <i>Exponential lower bounds for the pigeonhole principle</i>, Computational Complexity, Band 3, 1993, S. 97–140</li>
<li>mit Paul Beame: <i>Simplified and improved resolution lower bounds</i>, Proceedings of the 37th Annual Symposium on Foundations of Computer Science (STOC), 1996, S. 274–282</li>
<li>mit Maria Bonet, <a href="Ran_Raz" title="Ran Raz">Ran Raz</a>: <i>Lower bounds for cutting planes proofs with small coefficients</i>, Journal of Symbolic Logic, Band 62, 1997, S. 708–728</li>
<li>mit Paul Beame: <i>Propositional proof complexity: past, present, and future</i>, Bulletin of the European Association for Theoretical Computer Science, 1998, S. 66–89, nachgedruckt in: Current Trends in Theoretical Computer Science, World Scientific, 2001</li>
<li>mit Paul Beame, Richard Karp, Michael Saks: <i>On the complexity of unsatisfiability proofs for random k-CNF formulas</i>, Proceedings of the 30th ACM Symposium on Theory of Computing (STOC), 1998, S. 561–571</li>
<li>mit Paul Beame, Richard Karp, Michael Saks: <i>The efficiency of resolution and Davis-Putnam procedures</i>, SIAM Journal on Computing, Band 31, 2002, s. 1048–1075</li>
<li>mit <a href="Cynthia_Dwork" title="Cynthia Dwork">Cynthia Dwork</a>, <a href="Moni_Naor" title="Moni Naor">Moni Naor</a>, Guy N. Rothblum: <i>Differential privacy under continual observation</i>, Proceedings of the Forty-Second ACM Symposium on Theory of Computing (STOC), 2010, S. 715–724</li>
<li>mit Cynthia Dwork, Moritz Hardt, <a href="Omer_Reingold" title="Omer Reingold">Omer Reingold</a>, Richard Zemel: <i>Fairness Through Awareness</i>, Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12. New York, 2012, S. 214–226.</li>
<li>mit Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Omer Reingold, Aaron Roth: <i>The reusable holdout: Preserving validity in adaptive data analysis</i>, Science, Band 349, 2015, S. 636–638. <a class="external mw-magiclink-pmid" rel="nofollow" href="https://www.ncbi.nlm.nih.gov/pubmed/26250683?dopt=Abstract">PMID 26250683</a>.</li></ul>
<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>
<ul><li><a rel="nofollow" class="external text" href="https://www.cs.toronto.edu/~toni/">Webseite an der Universität Toronto</a></li></ul>
<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>
<ol class="references">
<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://www.mathgenealogy.org/id.php?id=80101">Toniann Pitassi</a> im <a href="Mathematics_Genealogy_Project" title="Mathematics Genealogy Project">Mathematics Genealogy Project</a> (englisch) <span style="display:none">Vorlage:MathGenealogyProject/Wartung/id verwendet</span></span>
</li>
<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://www.ias.edu/scholars/toniann-pitassi">Eintrag von Pitassi beim IAS</a></span>
</li>
<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text">Darstellung ihrer Forschung auf ihrer <a rel="nofollow" class="external text" href="https://www.cs.toronto.edu/~toni/">Webseite</a> an der Universität Toronto, abgerufen am 30. Mai 2022</span>
</li>
</ol>
</div><!--htdig_noindex--><div><div class="zim-footer">
Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2022-05-30" href="https://de.wikipedia.org/wiki/?title=Toniann_Pitassi&oldid=223290330">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
<script src="./_webp_/webpHandler.js"></script>
</body></html>